Brought to you by EarthWeb
IT Library Logo

Click Here!
Click Here!


Search the site:
 
EXPERT SEARCH -----
Programming Languages
Databases
Security
Web Services
Network Services
Middleware
Components
Operating Systems
User Interfaces
Groupware & Collaboration
Content Management
Productivity Applications
Hardware
Fun & Games

EarthWeb Direct EarthWeb Direct Fatbrain Auctions Support Source Answers

EarthWeb sites
Crossnodes
Datamation
Developer.com
DICE
EarthWeb.com
EarthWeb Direct
ERP Hub
Gamelan
GoCertify.com
HTMLGoodies
Intranet Journal
IT Knowledge
IT Library
JavaGoodies
JARS
JavaScripts.com
open source IT
RoadCoders
Y2K Info

Previous Table of Contents Next


HIERARCHICAL ROUTING FUNDAMENTALS

Hierarchical routing forms the core of CIDR. Before describing CIDR, a brief review of some of the fundamental concepts of hierarchical routing is necessary. Hierarchical routing is a technique that allows aggregation of addressing information. Aggregation of addressing information, in turn, allows to reduce the load on the routing system, thereby resulting in improved scalability of routing.

Hierarchical routing works by partitioning network topology into a set of connected segments, and then aggregating addressing information for all the nodes within each segment. This way a router within a given segment, while maintaining individual routes for every node within its own segment, does not need to maintain individual routes for individual nodes in other segments. Instead, the router could just maintain a single (aggregate) route for each other segment. This (aggregate) route would be sufficient to provide routing to all the nodes within the other segment.

An illustration of a network topology is shown in Exhibit 3-2-1. Without hierarchical routing, each node in the topology would need to maintain routes to all the other nodes in the topology—a total of 10 routes. By partitioning the topology into three segments, S1, S2, and S3, and aggregating addressing information within each segment, a node in S1 would need to maintain only five routes—three to the other nodes in S1, and two to the other two segments (S2 and S3). Likewise a node in S2 would need to maintain only four routes—two to the other nodes in S2, and two to the other two segments.


Exhibit 3-2-1.  Hierarchical Routing Configuration

The concept of hierarchical routing could be applied recursively—several connected segments could be combined into a single super-segment, and addressing information for all the nodes in this super-segment could be combined into a single route. It is precisely this recursion that makes the hierarchical routing so powerful with respect to its ability to improve scaling properties of the routing system. In an ideal case, with hierarchical routing the amount of addressing information that a router would need to maintain could scale logarithmically with the number of nodes in a network.

A common way of expressing aggregated addressing information is by address prefixes. An address prefix is an address with an indication of the number of the leftmost contiguous significant bits in the address. An address prefix is usually denoted as a/b, where a is an address, and b is the number of significant bits in the address. For example, 192.9.200.0/23 is an address prefix that covers a contiguous block of 512 IP addresses from 192.9.200.0 to 192.9.200.511.

Using hierarchical routing for aggregating addressing information imposes certain constraints on how addresses could be assigned. Specifically, addresses of the nodes within a segment have to be assigned in such a way as to make the aggregation possible. If the aggregated addressing information is expressed as address prefixes, this requirement implies that within a segment addresses of all the nodes that are aggregated into a given prefix must match this prefix. As the network topology changes, if such changes are spread across segments’ boundaries, to preserve the desired level of aggregation (and thereby the desired volume of routing information), the boundaries of segments may need to be changed (a node, or a group of nodes may have to move from one segment to another), and addresses of the nodes within the affected segments may need to be change as well (the process known as renumbering).

Exhibit 3-2-2 illustrates how hierarchical routing constraints address assignments. The addresses of all the nodes within S1 should be assigned in such a way as to be combined into a single address prefix. The same applies to the nodes in S2 and S3. A possible address assignment that meets this requirement is shown in Exhibit 3-2-2.


Exhibit 3-2-2.  A Possible Hierarchical Routing Constraints Address Assignment

With this address assignment, addresses of all the nodes in S1 could be aggregated into a single prefix 192.9.200.0/29, addresses of all the nodes in S2 could be aggregated into 198.8.15.0/30, and addresses of all the nodes in S3 could be aggregated into 201.10.65.0/29.

To show the implications of changes in the topology on address assignment, it must be assumed that as a result of such changes the node S1.3 is no longer connected to S1.3 and S1.4, but is still connected to S3.4. To maintain routing to S1.3, either other nodes would have to add to their routing tables an additional route to S1.3 (thereby increasing the total number of routes they have to maintain) or S1.3 should become part of S3 and change its address (e.g., to 201.10.65.5).


Previous Table of Contents Next

footer nav
Use of this site is subject certain Terms & Conditions.
Copyright (c) 1996-1999 EarthWeb, Inc.. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Please read our privacy policy for details.